package com.dylan.历史.领扣;

import java.util.HashMap;
import java.util.Map;

/**
 * @Auther: ankang
 * @Date: 2019/3/26 10:45
 * @Description:
 */
public class $0070爬楼梯 {

    public static void main(String[] args) {
        int f = new $0070爬楼梯.Solution().climbStairs(33);
        System.out.println(f);
    }

    static class Solution {
        private Map<Integer, Integer> cache = new HashMap();
        public int climbStairs(int n) {
            if(n==1) {
                return 1;
            }
            if(n==2) {
                return 2;
            }
            Integer stepN1 = cache.get(n-1);
            Integer stepN2 = cache.get(n-2);
            if(stepN1 == null) {
                stepN1 = climbStairs(n-1);
                cache.put(n-1, stepN1);
            }
            if(stepN2 == null) {
                stepN2 = climbStairs(n-2);
                cache.put(n-2, stepN2);
            }
            return stepN1+stepN2;
        }
    }
}
